//## begin module%3C6E5D050281.cm preserve=no
//	  %X% %Q% %Z% %W%
//## end module%3C6E5D050281.cm

//## begin module%3C6E5D050281.cp preserve=no
//	+----------------------------------------------+
//	| SVMBR - A program for training SVMs          |
//	+----------------------------------------------+
//	| * Creator, modeling, coding:                 |
//	|    Marcelo Barros de Almeida                 |
//	|    barros@smar.com.br                        |
//	|    http://litc.cpdee.ufmg.br/~barros/        |
//	| * Coding, improvements, bug fixes:           |
//	|    Bernardo Penna                            |
//	|    bprc@brfree.com.br                        |
//	+----------------------------------------------+
//
//	 Copyright(c) 2002 by Marcelo Barros de Almeida
//	                            All rights reserved
//
//	-[CVS]------------------------------------------
//	$Author$
//	$Date$
//	$Source$
//	$Name$
//	$Revision$
//	------------------------------------------------
//## end module%3C6E5D050281.cp

//## Module: pqueue%3C6E5D050281; Package body
//## Subsystem: <Top Level>
//## Source file: D:\textotese\svmbr\src\pqueue.cpp

//## begin module%3C6E5D050281.additionalIncludes preserve=no
//## end module%3C6E5D050281.additionalIncludes

//## begin module%3C6E5D050281.includes preserve=yes
//## end module%3C6E5D050281.includes

// pqueue
#include "pqueue.h"
//## begin module%3C6E5D050281.declarations preserve=no
//## end module%3C6E5D050281.declarations

//## begin module%3C6E5D050281.additionalDeclarations preserve=yes
//## end module%3C6E5D050281.additionalDeclarations


// Class PQueue 




PQueue::PQueue (INT sz)
  //## begin PQueue::PQueue%1013865831.hasinit preserve=no
  //## end PQueue::PQueue%1013865831.hasinit
  //## begin PQueue::PQueue%1013865831.initialization preserve=yes
  //## end PQueue::PQueue%1013865831.initialization
{
  //## begin PQueue::PQueue%1013865831.body preserve=yes
	size = sz;
	count = 0;
	itens = new heapItem [size];
  //## end PQueue::PQueue%1013865831.body
}


PQueue::~PQueue ()
{
  //## begin PQueue::~PQueue%1013865832.body preserve=yes
	delete itens;
  //## end PQueue::~PQueue%1013865832.body
}



//## Other Operations (implementation)
VOID PQueue::add (REAL val, INT idx)
{
  //## begin PQueue::add%1013865834.body preserve=yes

	itens[count].value = val;
	itens[count].index = idx;

	if(count == 0) {
		count++;
		return;
		}

	INT place = count;
	INT parent = (INT)((place-1)/2);
	heapItem hi;

	while((parent >= 0)&&(itens[place].value > itens[parent].value)) {
		hi = itens[parent];
		itens[parent] = itens[place];
		itens[place] = hi;
		place = parent;
		parent = (INT)((place-1)/2);
	}

	count++;

  //## end PQueue::add%1013865834.body
}

INT PQueue::remove (INT idx)
{
  //## begin PQueue::remove%1013865835.body preserve=yes

	if(count == 0) 
		return -1;
	
	heapItem hi = itens[idx];
	count--;
	itens[idx] = itens[count];
	rebuild(idx);

	return hi.index;

  //## end PQueue::remove%1013865835.body
}

VOID PQueue::rebuild (INT idx)
{
  //## begin PQueue::rebuild%1013865836.body preserve=yes

	INT child = 2*idx + 1;

	if(child < count) {

		INT rchild = child + 1;

		if((rchild < count)&&(itens[rchild].value > itens[child].value))
			child = rchild;

		if(itens[idx].value < itens[child].value) {
			heapItem hi = itens[idx];
			itens[idx] = itens[child];
			itens[child] = hi;
			rebuild(child);
		}

	}

  //## end PQueue::rebuild%1013865836.body
}

// Additional Declarations
  //## begin PQueue%3C694DA502CF.declarations preserve=yes
  //## end PQueue%3C694DA502CF.declarations

//## begin module%3C6E5D050281.epilog preserve=yes
//## end module%3C6E5D050281.epilog
